Many spell-check dictionaries represent words as a list of strings, sometimes with linguistic relationships represented by affix operations. For example, given the English word “party” and the information that the rule “some words ending in -y are pluralized by replacing -y with -ies” applies to this word, the validity of the word “parties” can be deduced. However, to check the spelling of a word, the most fundamental operation is simply to determine whether a given sequence of characters (e.g., a word in the English language) appears in the set of words included in a dictionary.
Simplistically, this type of dictionary might be modelled as a decision tree in which the first node represents the start of every legal word, and each node has one or more outgoing paths corresponding to a single legal character in the next position in the word, or a legal “end of string” state. However, this representation does not utilize memory very efficiently, nor lend itself to rapid search performance.